package org.example.sword2offer.primary;

import java.util.ArrayList;
import java.util.Stack;

/**
 * @author: lynn
 * @Descript: 二叉树中和为某一值的路径
 * 考点: 前序遍历的应用  https://www.jianshu.com/p/c661cbe1d421
 * @date: 2021/3/11 23:47
 * @version: 1.0
 */
public class Q24_FindPathBST {
    /**
     * 输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。
     * 路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
     * (注意: 在返回值的list中，数组长度大的数组靠前)
     */
    public static void main(String[] args) {
        TreeNode treeNode=new TreeNode(8);
        treeNode.left=new TreeNode(4);
        treeNode.right=new TreeNode(10);
        treeNode.left.left=new TreeNode(11);
        treeNode.left.right=new TreeNode(6);
        treeNode.right.left=new TreeNode(5);
        treeNode.right.right=new TreeNode(11);
        FindPath(treeNode,23);
        System.out.println("List:{}");
    }
    /**
     审题可知，我们需要有一个自上而下从根结点到每个叶子结点的遍历思路，而先序遍历刚好可以拿来用，
     我们只需在来到当前结点时将当前结点值加入到栈中，
     在离开当前结点时再将栈中保存的当前结点的值弹出即可使用栈模拟保存自上而下经过的结点，
     从而实现在来到每个叶子结点时只需判断栈中数值之和是否为target即可。
     */
    public static ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        ArrayList<ArrayList<Integer>> res = new ArrayList();
        if(root == null){
            return res;
        }
        Stack<Integer> stack = new Stack<Integer>();
        preOrder(root, stack, 0, target, res);
        return res;
    }

    public static void preOrder(TreeNode root, Stack<Integer> stack, int sum, int target,
                         ArrayList<ArrayList<Integer>> res){
        if(root == null){
            return;
        }

        stack.push(root.val);
        sum += root.val;
        //leaf node
        if(root.left == null && root.right == null && sum == target){
            ArrayList<Integer> one = new ArrayList();
            one.addAll(stack);
            res.add(one);
        }

        preOrder(root.left, stack, sum, target, res);
        preOrder(root.right, stack, sum, target, res);
        //移除已经计算过的树节点
        sum -= stack.pop();
    }

    private static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int val){
            this.val= val;
        }
    }
}
